package Hot100.leetcode.editor.cn.code.排序算法;

/**
 * 归并排序实现类
 */
public class MergeSort {
    /**
     * 归并排序入口方法
     * @param arr 待排序的数组
     */
    public static void mergeSort(int[] arr) {
        // 边界条件检查：空数组或只有一个元素的数组已经有序
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 创建临时数组，用于合并过程
        // 在整个排序过程中复用这个数组，避免重复创建数组的开销
        int[] temp = new int[arr.length];

        // 调用递归排序方法，对整个数组进行排序
        // 参数含义：arr-待排序数组, temp-临时数组, 0-起始索引, arr.length-1-结束索引
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    /**
     * 递归实现归并排序的核心方法
     * @param arr 待排序的数组
     * @param temp 用于合并的临时数组
     * @param left 当前排序区间的左边界（包含）
     * @param right 当前排序区间的右边界（包含）
     */
    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        // 递归终止条件：当左边界大于等于右边界时，表示区间内没有元素或只有一个元素
        if (left >= right) {
            return;
        }

        // 计算中间位置，避免整数溢出使用 left + (right - left) / 2 而不是 (left + right) / 2
        int mid = left + (right - left) / 2;

        // 递归排序左半部分 [left, mid]
        mergeSort(arr, temp, left, mid);

        // 递归排序右半部分 [mid+1, right]
        mergeSort(arr, temp, mid + 1, right);

        // 合并两个已排序的部分
        merge(arr, temp, left, mid, right);
    }

    /**
     * 合并两个已排序的子数组
     * 左半部分：[left, mid]
     * 右半部分：[mid+1, right]
     * @param arr 原数组
     * @param temp 临时数组
     * @param left 左边界
     * @param mid 中间位置
     * @param right 右边界
     */
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // 将当前需要合并的区间复制到临时数组中
        // 这样在合并过程中可以直接修改原数组而不会影响未处理的数据
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        int i = left;      // i 指向左半部分的起始位置
        int j = mid + 1;   // j 指向右半部分的起始位置
        int k = left;      // k 指向合并后数组的当前位置

        // 比较左右两部分的元素，将较小的元素放回原数组
        while (i <= mid && j <= right) {
            // 当左半部分的元素小于等于右半部分的元素时
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];  // 将左半部分元素放回原数组，并移动相应指针
            } else {
                arr[k++] = temp[j++];  // 将右半部分元素放回原数组，并移动相应指针
            }
        }

        // 将左半部分剩余的元素复制回原数组
        // 这些元素已经有序且都大于右半部分的所有元素
        while (i <= mid) {
            arr[k++] = temp[i++];
        }

        // 将右半部分剩余的元素复制回原数组
        // 这些元素已经有序且都大于左半部分的所有元素
        while (j <= right) {
            arr[k++] = temp[j++];
        }
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前:");
        printArray(arr);

        mergeSort(arr);

        System.out.println("排序后:");
        printArray(arr);
    }

    /**
     * 打印数组元素
     * @param arr 要打印的数组
     */
    private static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

